A one-way function is a function ƒ for which one can compute the value y=ƒ(x) given the value x, but for which it is computationally infeasible to compute the value x given y, unless a so-called “trap door” is known, where only particular one-way functions have trap doors. In the above context, the value x is called the pre-image of y, and the value y is called the image of x, both relative to the function ƒ. Examples of one-way functions include hash functions, such as the well-known SHA-1 and MD5 hashing algorithms, and functions for generating message authentication codes (MACs). For additional details regarding these and other one-way functions, see A. J. Menezes et al., “Handbook of Applied Cryptography,” CRC Press, 1997, which is incorporated by reference herein.
For many cryptographic applications, it is desirable to compute a so-called one-way chain. This is a sequence of values v1 . . . vs such that vi−1=ƒ(vi). More generally, vi−1=ƒ(g(vi)), where g is a function that maps input of the size of the output of a hash chain or other one-way function h to the size of the input of the function h. In particular, g could be a truncation of information to the right length, a padding of information to the right length, or other similar mapping function, as is well known to those skilled in the art. It is also known that if h is a function that accepts input of arbitrary length, as hash functions do, then there is no need to use the function g. Alternatively, one could say that g in such a situation is the identity function. In order to simplify the notation used herein, the potential use of the function g will not be shown explicitly, as this can be understood to be appropriately built into the functionality of the one-way function h, if needed.
It should also be noted that one may use different functions for different steps in the chain, where a “step” of the chain refers to generation of a given chain output value from a previous chain value. Similarly, one could allow auxiliary inputs to the various steps. For simplicity of illustration, these particular variants are not explicitly described herein, but those skilled in the art will recognize that one-way chains may be configured using these and other variants.
A one-way chain of the type described above can be computed by starting with value vs and from that value computing vs−1 by application of the one-way function to vs, then computing vs−2 by application of the one-way function to vs−1, and so on. This is a general case of computation of the above value y=ƒ(x), since the value y is used as input to the one-way function, in the next “link” of the chain. One important reason for using such chains is to represent time. For example, if a one-way chain v1 . . . vs is computed by a first party from an endpoint value vs, and the value v1 of the chain is given to a second party, then the first party can “increment time” by showing consecutive pre-images v2, v3, etc. to the second party. Note that the second party cannot compute these consecutive pre-images from v1 on its own. However, given a pre-image v2, the second party can verify the correctness of that pre-image by checking if v1=ƒ(v2). For v3, this verification would have two steps, a first in which v2 is computed, and a second in which v1 is computed and compared to the known value v1.
Another known use of one-way chains is as a representation of money or other payment mechanism in a micro-payments application. For example, if a first party generates a one-way chain and has it authenticated by a bank, e.g., via a digital signature on the endpoint vs of the chain, then the first party can pay a second party one unit of payment by revealing v2. The second party can take this value to the bank to obtain funds for it. The first party can pay a second unit to the second party by revealing v3, and so on. Note that this simple example is applicable to only a single payee.
One-way chains are also used in computing keys for verifying the authenticity of messages having MACs. See A. Perrig et al., “Efficient and Secure Source Authentication for Multicast,” Proceedings of Network and Distributed System Security Symposium NDSS 2001, February 2001, A. Perrig et al., “Efficient Authentication and Signing of Multicast Streams over Lossy Channels,” Proc. of IEEE Security and Privacy Symposium SP 2000, May 2000, and A. Perrig et al., “TESLA: Multicast Source Authentication Transform,” Proposed IRTF draft, all of which are incorporated by reference herein. In this approach, a device would compute and broadcast a message and its corresponding MAC during a first time interval, and then release the key during a later time interval. Recipients could verify the MAC after the key is released, and would trust the authenticity of the message based on the knowledge that only the sender could have known the key at the time the MAC was broadcast. The key is verified by applying a hash function to that key and comparing the result to a less recent key associated with the same chain, and therefore with the sender.
The conventional use of one-way chains in these and other applications suffers from a significant drawback, in that in order to output consecutive chain values, those values must be either stored or computed. If the values are to be output directly from storage without computation, the party generally must store all of the values. Alternatively, if the values are to be computed as needed, the party must compute a given value from the endpoint vs by iterated application of the function ƒ assuming ƒ is not a trap door function for which the party knows the trap door or wishes to use the trap door. In the case of storage without computation, the party needs to use storage proportional to the length s of the chain, or in other words, storage O(s), where O( ) denotes “on the order of.” In the case of computation as needed, the first party needs to use computation O(s).
This excessive storage-computation product associated with conventional one-way chain computation is particularly problematic in so-called “lightweight” processing devices, such as mobile telephones, smart cards, personal digital assistants (PDAs), and other types of wireless or portable devices, which generally have limited storage or computational resources, often due at least in part to the use of battery power in such devices. Other examples include so-called “smart dust” or “dust computers,” which refer to very small computational devices which can be used to collectively cover a large area for purposes of surveillance, e.g., seismic or military.
In these and many other cases, the storage or computational costs associated with conventional one-way chain computations make it difficult or impossible to implement standard cryptographic techniques in such devices.
A need therefore exists for improved techniques for computing consecutive pre-image values of one-way chains and other one-way graphs, such that the above-noted storage and computational costs are substantially reduced, thereby improving the efficiency of cryptographic techniques and permitting implementation of such techniques in lightweight processing devices.